package com.lmz.project.redis.arithmetic.sort;

import java.io.*;

/**
 * 归并排序
 */
public class MergeSort {
    /**
     * 1）填函数风格
     * 2）acm风格（笔试、比赛最常见）
     * a. 规定数据量(BufferedReader、StreamTokenizer、PrintWriter)，其他语言有对等的写法
     * b. 按行读(BufferedReader、PrintWriter)，其他语言有对等的写法
     * c. 不要用Scanner、System.out，IO效率慢
     * 3）不推荐：临时动态空间
     * 4）推荐：全局静态空间
     */
//
//    public static int MAX = 501;
//    public static int[] arr = new int[MAX];
//    public static int[] help = new int[MAX];
//
//    public static int n;
//    //测试链接:https://www.nowcoder.com/practice/bc25055fb97e4a0bb564cb4b214ffa92
//
//    public static void main(String[] args) throws IOException {
//        // 把文件里的内容，load进来，保存在内存里，很高效，很经济，托管的很好
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        // 一个一个读
//        StreamTokenizer in = new StreamTokenizer(br);
//        // 提交答案的时候用的，也是一个内存托管区
//        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
//        n = (int) in.nval;
//        //装填数组
//        for (int i = 0; i < n; i++) {
//            in.nextToken();
//            arr[i] = (int) in.nval;
//        }
//        //排序
//        mergeSort1(0, arr.length - 1);
//
//        for (int i = 0; i < n - 1; i++) {
//            out.print(arr[i] + " ");
//        }
//
//        out.flush();
//        out.close();
//        br.close();
//    }


    public static int MAX = 50001;
    public static int[] help = new int[MAX];

    public static int[] sortArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return nums;
        }
        int l = 0;
        int r = nums.length - 1;
        //递归方式
//        mergeSort1(nums, l, r);
        //非递归方式
        mergeSort2(nums);
        return nums;
    }


    public static void mergeSort1(int[] nums, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + (r - l) / 2;
        mergeSort1(nums, l, mid);
        mergeSort1(nums, mid + 1, r);
        //将这两个数组排序合并
        sortAsc(nums, l, mid + 1, r);
    }

    //测试地址:https://leetcode.cn/problems/sort-an-array/submissions/576940241/
    public static void sortAsc(int[] arr, int lstart, int rstart, int end) {
        int a = lstart;
        int l = lstart;
        int mid = rstart - 1;
        while (lstart <= mid && rstart <= end) {
            help[a++] = arr[lstart] <= arr[rstart] ? arr[lstart++] : arr[rstart++];
        }
        while (lstart <= mid) {
            help[a++] = arr[lstart++];
        }
        while (rstart <= end) {
            help[a++] = arr[rstart++];
        }
        //将有序数组重新刷入原数组中
        for (int i = l; i <= end; i++) {
            arr[i] = help[i];
        }
    }

    public static void merge(int[] arr, int l, int m, int r) {
        int i = l;
        int a = l;
        int b = m + 1;
        while (a <= m && b <= r) {
            help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        while (a <= m) {
            help[i++] = arr[a++];
        }
        while (b <= r) {
            help[i++] = arr[b++];
        }
        for (i = l; i <= r; i++) {
            arr[i] = help[i];
        }
    }

//    public static void mergeSort2(int[] nums) {
//        //定义一个步长，每次增长一倍，知道超过数组的最大长度
//        int step =1;
//        for (int i = 0; step < nums.length; i++, step <<= 1) {
//            int left = 0;
//            int right = 0;
//            int j = 0;
//            while (left + step < nums.length) {
//                left = j * step;
//                right = (j + 1) * step - 1 <= nums.length -1 ? (j + 1) * step - 1 : nums.length -1;
//                int mid = left + (right - left) / 2;
//                sortAsc(nums, left, mid + 1, right);
//                j++;
//            }
//        }
//    }

    public static void mergeSort2(int[] arr) {
        int n = arr.length;
        for (int l, m, r, step = 1; step < n; step <<= 1) {
            l = 0;
            while (l < n) {
                m = l + step - 1;
                if (m + 1 >= n) {
                    break;
                }
                r = Math.min(l + (step << 1) - 1, n - 1);
                sortAsc(arr, l, m+1, r);
                l = r + 1;
            }
        }
    }


    public static void main(String[] args) {
        //[5,2,3,1]
        int[] nums = {-74,48,-20,2,10,-84,-5,-9,11,-24,-91,2,-71,64,63,80,28,-30,-58,-11,-44,-87,-22,54,-74,-10,-55,-28,-46,29,10,50,-72,34,26,25,8,51,13,30,35,-8,50,65,-6,16,-2,21,-78,35,-13,14,23,-3,26,-90,86,25,-56,91,-13,92,-25,37,57,-20,-69,98,95,45,47,29,86,-28,73,-44,-46,65,-84,-96,-24,-12,72,-68,93,57,92,52,-45,-2,85,-63,56,55,12,-85,77,-39};
        int[] ints = sortArray(nums);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i] + " ");
        }
    }
}
